package Solution.problem047;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program Leetcode
 * @description:
 * @author: lishangsheng
 * @create: 2019/03/31 14:43
 */
public class Solution {
    public static List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        do {
            List<Integer> tmp = new ArrayList<Integer>();
            for (int num : nums) {
                tmp.add(num);
            }
            ans.add(tmp);
        } while (nextPermutation(nums));
        return ans;
    }

    /**
     * 找到数据的下一个排列方式
     * @param nums
     * @return
     */
    private static boolean nextPermutation(int[] nums){
        if(nums.length==1){
            return false;
        }

        /** 从末尾开始找到一个可以交换的为止，因为是排序好的，只需要前面一位小于后面一位就可以了*/
        int p=-1;
        for(int i=nums.length-2;i>=0;i--){
            if(nums[i]<nums[i+1]){
                p=i;
                break;
            }
        }
        /** 如果p是-1的话，证明已经是最大了，找不到下一个了，降序排列了*/
        if(p==-1){
            return false;
        }

        int tmp=nums[p];
        int q = nums.length - 1;
        while (nums[q] <= tmp) {
            q--;
        }
        nums[p]=nums[q];
        nums[q]=tmp;
        reverse(p+1,nums);
        return true;
    }


    public static void reverse(int k, int[] nums) {
        if (k >= nums.length) return;
        int i = k;
        int j = nums.length - 1;
        while (i < j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
            i++;
            j--;
        }
    }
    public static void main(String[] args){
        int[] arry=new int[]{1,1,2};
        List<List<Integer>> list=permuteUnique(arry);
        System.out.println(list);
    }
}
